package com.zjsru.oneDay;

import java.util.ArrayList;
import java.util.List;

/**
 * 累加数
 *
 *
 * 输入："112358"
 * 输出：true
 * 解释：累加序列为: 1, 1, 2, 3, 5, 8 。1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8
 *
 * 输入："199100199"
 * 输出：true
 * 解释：累加序列为: 1, 99, 100, 199。1 + 99 = 100, 99 + 100 = 199
 *
 * */
public class isAdditiveNumber {
    String num;
    int n;
    List<List<Integer>> list = new ArrayList<>();
    public boolean isAdditiveNumber(String _num) {
       num = _num;
       n = num.length();
       return dfs(0);
    }
    boolean dfs(int u){
        int m = list.size();
        if(u == n) return m >= 3;
        int max = num.charAt(u) == '0' ? u+1 :n;
        List<Integer> cur = new ArrayList<>();
        for (int i = u; i < max ; i++) {
            cur.add(0, num.charAt(i) - '0');
            if (m < 2 || check(list.get(m - 2), list.get(m - 1), cur)) {
                list.add(cur);
                if (dfs(i + 1)) return true;
                list.remove(list.size() - 1);
            }
        }
            return false;
        }
    boolean check(List<Integer> a, List<Integer> b, List<Integer> c) {
        List<Integer> ans = new ArrayList<>();
        int t = 0;
        for(int i =0;i < a.size() || i < b.size();i++){
            if(i < a.size()) t += a.get(i);
            if(i < b.size()) t += b.get(i);
            ans.add(t % 10);
            t /= 10;
        }
        if(t >0) ans.add(t);
        boolean ok = c.size() == ans.size();
        for(int i = 0;i < c.size() && ok;i++){
            if(c.get(i) != ans.get(i)) ok = false;
        }
        return ok;
    }
    public static void main(String[] args){
        isAdditiveNumber isAdditiveNumber = new isAdditiveNumber();
        String num = "199100199";
        System.out.println(isAdditiveNumber.isAdditiveNumber(num));
    }
}
